package org.example.symbol;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) throws Exception {
        String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
        HeapSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(Comparable[] source) {
        Comparable[] heap = new Comparable[source.length + 1];

        createHeap(source, heap);

        int N = heap.length - 1;

        while (N != 1) {
            exch(heap, 1, N);
            N--;
            sink(heap, 1, N);
        }
        System.arraycopy(heap, 1, source, 0, source.length);
    }

    private static void sink(Comparable[] heap, int i, int n) {
        while (2 * i<= n) {
            int max =2*i;
            if (2*i+1<=n){
                if (heap[2*i].compareTo(heap[2*i+1])<0){
                    max=2*i+1;
                }
            }
            if (heap[i].compareTo(heap[max])<0){
                exch(heap,i,max);
            }
            i=max;
        }
    }

    private static void exch(Comparable[] heap, int i, int n) {
        Comparable temp = heap[i];
        heap[i] = heap[n];
        heap[n] = temp;
    }

    private static void createHeap(Comparable[] source, Comparable[] heap) {
//1.把source中的数据拷贝到heap中，从heap的1索引处开始填充
        System.arraycopy(source, 0, heap, 1, source.length);
//2.从heap索引的一半处开始倒叙遍历，对得到的每一个元素做下沉操作
        for (int i = (heap.length - 1) / 2; i > 0; i--) {
            sink(heap, i, heap.length - 1);
        }
    }
}
